﻿using System;

namespace SortOf
{
    public class LinkedList<T> where T : IComparable
    {
        protected LinkedListNode<T> header;

        public LinkedList(T headerElement)
        {
              this.header = new LinkedListNode<T>(headerElement);
        }

        // move through a linked list to find a Node
        private LinkedListNode<T> Find(T item)
        {
            // instantiate a Node object - current
            LinkedListNode<T> current = new LinkedListNode<T>();
            // assing it as the header node
            current = header;
            // check to see if the value in the node's Element field equals
            // the value we're searching for
            while((current.Element).CompareTo(item) != 0)
            {
                // if not, we move to the next node by assigning the node in
                // the Link field of current as the new value of current
                current = current.Link;
            }
            return current;
        }

        // once we've found the "after" node, the next step is to set the new 
        // node's Link field to the Link field of the "after" node, and then
        // set the "after" node's Link field to a reference to the new node

        public void Insert(T newItem, T after)
        {
            // instantiate a new Node object - current (null - null)
            LinkedListNode<T> current = new LinkedListNode<T>();
            // instantiate a new Node object - newNode (newItem - null)
            LinkedListNode<T> newNode = new LinkedListNode<T>(newItem);
            // find the after Node and assign it to current
            current = Find(after);
            // assign current.Link to newNode.Link
            newNode.Link = current.Link;
            // assign newNode to current.Link 
            current.Link = newNode;
        }

        // to remove a node from a linked list, we simply have to change the link
        // of the node that points to the removed node to point to the node after
        // the removed node. we'll define a method, FindPrevious, that does this.
        // this method walks down the list, stopping at each node and looking
        // ahead to the next node to see if that node's Element field holds the
        // item we want to remove

        private LinkedListNode<T> FindPrevious(T n)
        {
            LinkedListNode<T> current = header;
            while (!(current.Link == null) && ((current.Link.Element).CompareTo(n) != 0))
            {
                current = current.Link;
            }
            return current;
        }

        public void Remove(T n)
        {
            LinkedListNode<T> p = FindPrevious(n);
            if (!(p.Link == null))
            {
                p.Link = p.Link.Link;
            }
        }

        public void PrintList()
        {
            LinkedListNode<T> current = new LinkedListNode<T>();
            current = header;
            while (!(current.Link == null))
            {
                Console.WriteLine(current.Link.Element);
                current = current.Link;
            }
        }
    }
}
